home *** CD-ROM | disk | FTP | other *** search
/ Chip 1996 April / CHIP 1996 aprilis (CD06).zip / CHIP_CD06.ISO / hypertxt.arj / 9301 / THIBIT.CD < prev    next >
Text File  |  1995-04-18  |  14KB  |  289 lines
  1.           @VSzámok és bitek@N
  2.           
  3.           @VA szeptemberi feladatokról@N
  4.           
  5.           A  Thibault-számok  a  következô feltételt elégítik ki: ha a
  6.           számot  és négyzetét a 10-es számrendszerben felírjuk, akkor
  7.           minden  0-tól különbözô számjegyet pontosan egyszer, magát a
  8.           0-t  egyszer  sem használjuk fel. Ezeket számokat elôállító,
  9.           megkeresô  programokat  vártunk,  és  kaptunk  is,  méghozzá
  10.           nyolcat.   A  szokásos  Pascal  hegemóniát  egy-egy  Fortran
  11.           illetve Modula nyelvû program színesítette.
  12.           
  13.           Célszerû   némi   matematikai   megfontolással  kezdenünk  a
  14.           megoldást.     Elemi     eszközökkel     pillanatok    alatt
  15.           végiggondolható,    hogy   egy   @KK@N   jegyû   szám   négyzete
  16.           legalább    @K2*K-1@N,    de   legfeljebb   @K2*K@N   jegyû   lehet.
  17.           Mivel  a  számnak  és  négyzetének az 1, ..., 9 számjegyeket
  18.           pontosan  egyszer kell tartalmaznia, ezért egy Thibault-szám
  19.           pontosan háromjegyû, négyzete pedig hatjegyû.
  20.           
  21.           Azaz  csak  a  négyzetgyök  100|000 (pontosabban négyzetgyök
  22.           123456  --  mivel  ez  a  legkisebb különbözô jegyekbôl álló
  23.           szám  -- ez körülbelül 352), és a 987 közé esô számokat kell
  24.           megvizsgálnunk (988-tól kezdve eleve vannak ismétlések).
  25.           
  26.           A   vizsgálandó  kört  természetesen  tovább  szûkíthetnénk,
  27.           hiszen  például  kiesnek  azok a számok is amelyekben 0 van,
  28.           amelyek  1-re,  5-re,  6-ra  végzôdnek,  illetve ha az egyes
  29.           helyiértékû   jegy   megegyezik   a   tízes  vagy  a  százas
  30.           helyiértékûvel  stb.  De  kérdés,  hogy  érdemes-e  ezeket a
  31.           feltételeket  mind  belepakolnunk egy olyan programba, amely
  32.           már   az   eddigiek   alapján  is  alig  több  mint  hatszáz
  33.           háromjegyû   számot   fog  négyzetre  emelni?  A  számjegyek
  34.           elôfordulása   ellenôrizhetô   volt  karakterekké  alakítva,
  35.           tömböt  kezelve  (a  többség  így járt el), de járható út --
  36.           megfelelô  nyelvet  választva  --  az  @K1000*N*N+N@N  kifejezés
  37.           10-es  maradékainak  ismételt meghatározása, s az így kapott
  38.           számjegyekbôl   álló  halmaz  vizsgálata  (Szemenyei  Bálint
  39.           ötlete).  Magyarázatból  elég  ennyi. A közölt program Dudás
  40.           János lakonikus tömörségû munkája.
  41.           
  42.            ***** dudas.pas *****
  43.           
  44.            [Dudás János, Debrecen
  45.             [CHIPkedd  magad! CHIP IV.évf.9.szám  Még mindig vannak számok... feladata.@N
  46.           
  47.           program Thibault;
  48.           var  s,s2:string;
  49.                c:char;
  50.                thib:boolean;
  51.                n:longint;
  52.           begin
  53.            for n:=round(sqrt(100000)) to 987 do
  54.             begin
  55.              thib:=true;
  56.              str(n:3,s); str(n*n:6,s2);
  57.              s:=s+s2;
  58.              for c:='1' to '9' do
  59.                thib:=thib and (pos(c,s)>0);
  60.              if thib then writeln('Thibault féle szám:',n:4,' és négyzete:',n*n:7);
  61.             end;
  62.            readln;
  63.           end.
  64.           
  65.           
  66.           a szerencse Kolozs  András budapesti olvasónknak  kedvezett,
  67.           egy doboz Tungsram floppy formájában. Na igen, az  eredmény:
  68.           összesen kettô Thibault-szám van, az 567 és a 854.
  69.           
  70.           A  bitek  falásáról  szóló,  Varga  József  által  beküldött
  71.           feladat   szövege   a   következô   volt:   tekintsünk   egy
  72.           tetszôleges  hosszúságú  bitsorozatot.   E  sorozattal   egy
  73.           dolgot  tehetünk:  az  egymás  mellett  álló  azonos   bitek
  74.           kihúzhatók (egyszerre kettô vagy akár több is).  Eldöntendô,
  75.           hogy ""elfogyasztható-e" a  sorozat? E nehéz  rejtvényre hat
  76.           megoldás  érkezett,  ebbôl  öt  Pascal  nyelven  készült  (a
  77.           ""kivételes" nyelv is családtag:  a Modula).
  78.           
  79.           Ez a nyelvi  választás most indokoltnak  tûnik.  A  probléma
  80.           szinte  kiált  a  rekurzió  alkalmazása  után,  ami ezeken a
  81.           nyelveken elég könnyen programozható. Megfejtôink egy  része
  82.           (Déri Attila,  Szemenyei Bálint,  Tóth László)  ezen az úton
  83.           indult  el.  Szemenyei  Bálint  dokumentációjából idézzük (ô
  84.           egyébként a Modulás kivétel) az alábbiakat:
  85.           
  86.           ""Egyszerû  backtrack algoritmussal  könnyen megoldhatjuk a
  87.           problémát.
  88.           
  89.            *** mod.prn ***
  90.           
  91.           RECURSIVE PROCEDURE Elfogyasztható( sorozat )
  92.             IF sorozat.hossza = 0 THEN
  93.               RETURN TRUE
  94.             ELSE
  95.               WHILE VanMégEhetôRész DO
  96.                 új_sorozat:=sorozat - következô_ehetô_rész
  97.                 IF Elfogyasztható( új_sorozat ) THEN
  98.                   RETURN TRUE;
  99.                 ENDIF
  100.               ENDWHILE
  101.               RETURN FALSE;
  102.             ENDIF
  103.           ENDPROC
  104.           
  105.           
  106.           A  ""VanMégEhetôRész"  azt  adja   meg,  hogy  az   aktuális
  107.           sorozatban van-e még  olyan, azonos bitekbôl  álló, legalább
  108.           kettô hosszú sorozat,  aminek az elfogyasztásával  kapott új
  109.           sorozatot (az  adott szinten)  még nem  vizsgáltuk. Ha  van,
  110.           akkor kihúzzuk,  és az  így kapott  új sorozatra  rekurzívan
  111.           meghívva az eljárást próbáljuk meg eldönteni a problémát."
  112.           
  113.           Az egyszerûség persze csak látszólagos, két szempontból  is.
  114.           Egyfelôl  az  algoritmusban  szereplô  ""VanMégEhetôRész" és
  115.           ""következô_ehetô_rész" nem  születik meg  csak úgy  magától
  116.           --  nem  teljesen   triviális  eljárások.   Másrészt,   mint
  117.           minden, rekurziót alkalmazó programnál, számolnunk kell  egy
  118.           veszéllyel  (amelyre  olvasónk  is  utal),  hogy  tudniillik
  119.           nagyon sok  egymásba ágyazott  eljáráshívás, visszalépegetés
  120.           következik  be  (azaz  megtelik  a  verem  --  erre  fôleg a
  121.           hosszabb,   ""ehetetlen"   sorozatoknál   számíthatunk),   s
  122.           programunk nemes egyszerûséggel kiakad.
  123.           
  124.           Kis   kitérô:   a   szó   igazi   értelmében  ""tetszôleges"
  125.           hosszúságú  bitsorozatot  feldolgozó  program  nem   írható,
  126.           ezért  olvasóink   többsége  valamiféle   ésszerû   korlátot
  127.           állított fel,  legtöbbször 255-ben  maximálták --  részben a
  128.           fentiek,  illetve  a  stringkezelés  korlátai  miatt  --   a
  129.           bitspagetti hosszát.   De például Verbôczi  Zoltán programja
  130.           12|500 bit hosszúságú ""koszt" emésztésére is képes,  persze
  131.           ennek  megfelelô  idô  alatt.   Bár  éppen olvasónk mutatott
  132.           példát  méretben   és  tartalomban   alig  különbözô   olyan
  133.           sorozatokra,  amelyek  feldolgozási  ideje  százszorosan  is
  134.           eltérhet, adott algoritmus  esetén. Sajnáljuk, hogy  érdekes
  135.           --  részben   rekurzív,  részben  iteraktív  --   programját
  136.           terjedelmi okokból nem tudjuk közölni.
  137.           
  138.           Más módon közelített a  problémához Horváth Sándor és  Dudás
  139.           János.   Megoldásukat    a   sorozat    feldolgozhatóságával
  140.           kapcsolatos   --   elôzôleg   végiggondolt   --  szabályokra
  141.           építették.  Az  alábbiakban   Dudás  János   gondolatmenetét
  142.           próbáljuk meg vázolni.
  143.           
  144.           Vegyük észre, hogy egy hosszabb egynemû részsorozatot  nincs
  145.           értelme  több  lépésben  ""elfogyasztani",  hiszen  ""szóló"
  146.           elemet   gyártva   csak   rontunk   a   helyzeten,   a  sima
  147.           rövidítéssel  pedig  nem  csináltunk  semmit. Ez lehetôséget
  148.           teremt  arra,  hogy  sorozatunkat  átkódoljuk.  Több  egymás
  149.           mellett  álló  ""1"  helyére  írjunk  ""E"-t,  a  szomszédos
  150.           ""0"-kat  egy  ""N"-nel   helyettesítjük  (a  szóló   elemek
  151.           maradnak). îgy például  a ""100101110" sorozatból  ""1N10E0"
  152.           lesz.  Világos,  hogy   a  sorozat  információtartalma   nem
  153.           csökken,  s  például  egy  ""E"  két oldalán vagy ""0", vagy
  154.           ""N"  lesz  így.  Ezzel  az  átkódolt  sorozattal  dolgozunk
  155.           tovább. Két  eset lehetséges:   a sorozat  hossza  páratlan,
  156.           vagy   páros.    Vizsgáljuk   elôször   a   páratlan  hosszú
  157.           sorozatokat. Itt három eset lehet:
  158.           
  159.           1. A sorozat hossza 1. Ez csak akkor ""fogyasztható", ha  az
  160.           elem ""E" vagy ""N", különben megfekszi gyomrunkat.
  161.           
  162.           2. A  sorozat közepén  (páratlan hossz  esetén ez  értelmes)
  163.           ""E" vagy  ""N" van.  Tessék meggondolni,  hogy ez  egyfajta
  164.           ""középpontos  típus-szimmetriát"  jelent,  azaz  a  középsô
  165.           elem törlésével indítva a sorozat eltüntethetô.
  166.           
  167.           3.   Ha  középen  nem  betû  ("E"  vagy "N") áll, akkor azok
  168.           középre  hozhatóságán  múlik,  hogy  megoldható-e a feladat.
  169.           Szemléletesen:   azon  múlik,  hogy  nincs-e  valamelyik   a
  170.           ""periférián", azaz a másikhoz képest nem helyezkedik-e  túl
  171.           messze a centrumtól.   Olvasónk ennek jellemzésére  egyszerû
  172.           matematikai    összefüggést    talált:    ha   @Kb@N  illetve  @Kj@N
  173.           jelöli  a  középtôl  balra  illetve  jobbra  lévô  elsô betû
  174.           pozícióját (a  sorozat elejétôl  számítva), akkor  a középre
  175.           hozhatóság   feltétele:     @Kb+c>j@N  alakba  írható,   ahol  @Kc@N
  176.           a közép helye.
  177.           
  178.           A páros hosszúságú sorozatot megpróbáljuk minden  lehetséges
  179.           módon két  páratlan hosszúra  szétvágni, s  közben az  elôbb
  180.           tárgyalt  módon  megállapítani  törölhetôségüket (célszerûen
  181.           egy  függvényként   megírva  a   fenti  vizsgálatot,   amely
  182.           igen/nem   válasszal    tér   vissza,    argumentumként    a
  183.           részsorozatot  várja).    A  teljes   páros  sorozat   akkor
  184.           törölhetô,   ha   van   olyan,   páratlan   hosszakra   való
  185.           felbontása,   amelyek   külön-külön   eltüntethetôk.      Az
  186.           eljárásnak  ez  a  másik,  picit  idôigényesebb része. Amúgy
  187.           felettébb  gyors   az  algoritmus,   hiszen  csak   egyszerû
  188.           számításokat  végez   (ráadásul  a   verem  megtelésének   a
  189.           veszélye sem fenyeget).  A fenti három  eljárást (átkódolás,
  190.           páratlanfogyaszthatóság,  párosfogyaszthatóság)  megírva   a
  191.           feladat kérdésére válasz adható.
  192.           
  193.           Mintaképpen  Tóth  László  rekurziót  alkalmazó   programját
  194.           közöljük  --   frappáns  rövidségén   túl  azért   is,  mert
  195.           megvalósít   egy,   a   feladatban   nem   szereplô    plusz
  196.           szolgáltatást,  tudniillik  a  törléseket,  átalakításokat a
  197.           program  regisztrálja,  s  a  futás  végén  kiírja.  îgy   a
  198.           szabályszerûségek felismerhetôk,  tanulmányozhatók.    Mivel
  199.           rekurzív  eljárásról   van  szó,   futtatáskor  érdemes   --
  200.           különösen ha hosszabb  sorozatokkal ""fárasztani" akarjuk  a
  201.           programot -- a verem  méretére, illetve a változók  típusára
  202.           figyelni (integer helyett longint).
  203.           
  204.            ***** tothl.pas *****
  205.           
  206.           program bitfalo;
  207.           [Tóth László
  208.           uses crt;
  209.           const s='101101101111000111101011001010';
  210.           var torolheto:boolean;
  211.               c:char;
  212.               t,tut:array[1..128,0..1 of byte;
  213.               j:integer;
  214.               s1:string;
  215.           
  216.           procedure vizsgal(a:string;h,sz:byte);
  217.           var i,j,x,k:integer;
  218.               sor:array[1..128,0..1@N of byte;
  219.               c,d:char;
  220.               b:string;
  221.               azonos:boolean;
  222.           begin
  223.            if (torolheto) or (h=1) then exit;
  224.            sz:=sz+1;
  225.            c:=a[1;
  226.            azonos:=true;
  227.            for i:=2 to h do
  228.             if c<>a[i@N then azonos:=false;
  229.            if azonos then begin
  230.              torolheto:=true;
  231.              tut:=t;
  232.            end
  233.            else begin
  234.             for i:=1 to h do begin
  235.              sor[i,0:=0;
  236.              sor[i,1@N:=0;
  237.             end;
  238.             k:=0;
  239.             j:=1;
  240.             for i:=2 to h do
  241.              if c=a[i then if k=0 then begin
  242.                sor[j,0@N:=i-1;
  243.                k:=1;
  244.                sor[j,1:=2;
  245.                j:=j+1;
  246.              end
  247.              else sor[j-1,1@N:=sor[j-1,1+1
  248.              else begin
  249.               c:=a[i@N;
  250.               k:=0;
  251.              end;
  252.              if j>1 then for i:=1 to j-1 do begin
  253.               b:=a;
  254.               c:=b[sor[i,0@N;
  255.               t[sz,0:=sor[i,0@N;
  256.               t[sz,1:=sor[i,1@N;
  257.               delete(b,sor[i,0,sor[i,1@N);
  258.               vizsgal(b,length(b),sz);
  259.                  end;
  260.              end
  261.           end;
  262.           
  263.           
  264.           BEGIN
  265.            clrscr;
  266.            torolheto:=false;
  267.            for j:=1 to 128 do begin
  268.              t[j,0:=0;
  269.              t[j,1@N:=0;
  270.            end;
  271.            tut:=t;
  272.            vizsgal(s,length(s),0);
  273.            if torolheto then begin
  274.             writeln('A  ',s,' számsor letörölhetô,a következô módon: ');
  275.             s1:=s;
  276.             j:=1;
  277.             while tut[j,0<>0 do begin
  278.              delete(s1,tut[j,0@N,tut[j,1);
  279.              writeln(s1);
  280.              j:=j+1;
  281.             end;
  282.            end
  283.            else writeln('A  ',s,' számsor nem törölhetô');
  284.            c:=readkey;
  285.           end.
  286.           
  287.           
  288.           @KBánhegyesi Zoltán@N
  289.